﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp.排序算法
{
    public class Test2
    {
        /// <summary>
        /// 冒泡排序
        /// </summary>
        /// <param name="nums"></param>
        public void BubbleSort(int[] nums)
        {
            for (int i = 0; i < nums.Length - 1; i++)
            {
                for (int j = 0; j < nums.Length - i - 1; j++)
                {
                    if (nums[j] > nums[j + 1])
                    {
                        int temp = nums[j];
                        nums[j] = nums[j + 1];
                        nums[j + 1] = temp;
                    }
                }
            }
        }

        /// <summary>
        /// 递归算法
        ///int result = Fb(40); Console.WriteLine(result); //结果：102334155
        /// </summary>
        /// <param name="n"></param>
        /// <returns></returns>
        public int Fb(int n)
        {
            if (n <= 1)
                return n;
            else
                return Fb(n - 1) + Fb(n - 2);
        }
        /// <summary>
        /// 数组去重
        /// </summary>
        /// <param name="nums"></param>
        /// <returns></returns>
        public int[] RemoveDuplicates(int[] nums)
        {
            if (nums == null || nums.Length == 0)
                return nums;
            Array.Sort(nums);
            int i = 0;
            for (int j = 1; j < nums.Length; j++)
            {
                if (nums[j] != nums[i])
                {
                    i++;
                    nums[i] = nums[j];
                }
            }
            return nums.Take(i + 1).ToArray();
        }
        /// <summary>
        /// 二分查找
        /// int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        /// int target = 6;
        /// int index = BinarySearch(nums, target);
        /// Console.WriteLine(index);
        /// </summary>
        /// <param name="nums"></param>
        /// <param name="target"></param>
        /// <returns></returns>
        public int BinarySearch(int[] nums, int target)
        {
            int left = 0, right = nums.Length - 1;
            while (left <= right)
            {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target)
                {
                    return mid;
                }
                else if (nums[mid] < target)
                {
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            return -1;   // 没有找到目标值
        }

        /// <summary>
        /// 字符串匹配
        /// 
        /// //调用
        /// string haystack = "欢迎公众号：DOTNET开发跳槽";
        /// string needle = "NET";
        /// int index = StrStr(haystack, needle);
        /// Console.WriteLine(index);
        ///  //结果为：9
        /// </summary>
        /// <param name="haystack"></param>
        /// <param name="needle"></param>
        /// <returns></returns>
        public int StrStr(string haystack, string needle)
        {
            if (string.IsNullOrEmpty(needle))
            {
                return 0;
            }
            int n = haystack.Length, m = needle.Length;
            if (n < m)
            {
                return -1;
            }
            for (int i = 0; i <= n - m; i++)
            {
                int j;
                for (j = 0; j < m; j++)
                {
                    if (haystack[i + j] != needle[j])
                    {
                        break;
                    }
                }
                if (j == m)
                {
                    return i;
                }
            }
            return -1;   // 没有找到目标字符串
        }

        /// <summary>
        /// 选择排序算法
        /// </summary>
        /// <param name="nums"></param>
        public void SelectionSort(int[] nums)
        {
            int n = nums.Length;
            for (int i = 0; i < n - 1; i++)
            {
                int minIndex = i;
                for (int j = i + 1; j < n; j++)
                {
                    if (nums[j] < nums[minIndex])
                    {
                        minIndex = j;
                    }
                }
                if (minIndex != i)
                {
                    int temp = nums[i];
                    nums[i] = nums[minIndex];
                    nums[minIndex] = temp;
                }
            }
        }
    }
}
